#include <iostream>
#include<vector>
using namespace std;

int main() {
    vector<int> nums(100001, 0);
    nums[1] = 1;
    nums[2] = 2;
    for (int i = 3; i <= 100000; ++i)
        nums[i] = (nums[i - 2] + nums[i - 1]) % 1000000;
    int n = 0;
    while (cin >> n)
    {
        //cout << nums[n] << endl;
        if (n < 29)
            cout << nums[n] << endl;
        else
            printf("%06d\n", nums[n]);
    }
    return 0;
}